import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: CC31 三角形
 * <a href="https://www.nowcoder.com/practice/2b7995aa4f7949d99674d975489cb7da?tpId=46&tqId=29060&tPage=2&rp=2&ru=/ta/leetcode&qru=/ta/leetcode/question-rankin">...</a>
 * User: DELL
 * Date: 2023-05-07
 * Time: 16:31
 */
public class Solution {
    /**
     * 解法一 (动态规划)(自顶向下)
     * 时间复杂度: O(N^2)
     * 空间复杂度: O(N^2)
     * 状态定义: dp[i][j] = 从 (0,0) 到 (i,j) 的最小路径和
     * 状态转移: 当 j == 0 时: dp[i][j] = dp[i-1][j] + triangle[i][j]
     *         当 j == i 时: dp[i][j] = dp[i-1][j-1] + triangle[i][j]
     *         (这里是因为是三角形,当 j==i 时,(i-1,j) 是不在三角形之中的)
     *         其余情况时: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
     * 初始化: dp[0][0] = triangle[0][0]
     * 返回值: 返回 dp 最后一行中的最小值即可
     * @param triangle
     * @return
     */
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        //检验合法性
        if (triangle == null || triangle.size() == 0) {
            return -1;
        }
        int len = triangle.size();
        int[][] dp = new int[len][len];
        //初始化
        dp[0][0] = triangle.get(0).get(0);
        //状态转移
        for (int i = 1; i < len; i++) {
            //当 j == 0 时
            dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
            //当 i == j 时
            dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
            }
        }
        //得到最小值
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            min = Math.min(dp[len-1][i],min);
        }
        return min;
    }

    /**
     * 解法二 (主要针对解法一的空间复杂度进行优化)(自顶向下)
     * 时间复杂度: O(N^2)
     * 空间复杂度: O(N)
     * 通过对解法一的观察不难发现,每次进行状态转移的时候,都是只和 dp 数组上一行靠左边的元素有关,
     * 因此我们可以将 dp 数组优化位一维数组,同时每次进行状态转移的时候都是从右向左进行状态转移,
     * 这样子原上一行的数组就在 dp 数组中,只需要进行不断迭代即可.
     * @param triangle
     * @return
     */
    public int minimumTotal2(ArrayList<ArrayList<Integer>> triangle) {
        //检验合法性
        if (triangle == null || triangle.size() == 0) {
            return -1;
        }
        int len = triangle.size();
        int[] dp = new int[len];
        //初始化
        dp[0] = triangle.get(0).get(0);
        //状态转移
        for (int i = 1; i < len; i++) {
            //当 i == j 时
            dp[i] = dp[i-1] + triangle.get(i).get(i);
            //当 i != j 且 i != 0 时 (这里需要从右向左遍历)
            for (int j = i-1; j > 0; j--) {
                dp[j] = Math.min(dp[j-1], dp[j]) + triangle.get(i).get(j);
            }
            //当 j == 0 时
            dp[0] = dp[0] + triangle.get(i).get(0);
        }
        //得到最小值
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            min = Math.min(dp[i],min);
        }
        return min;
    }

    /**
     * 解法三 (针对解法二的时间进行优化) (自底向上)
     * 时间复杂度: O(N^2)
     * 空间复杂度: O(N)
     * 我们在这里可以考虑一下,从最上面走到最下面的最小路径和 和 从最下面走到最上面的最小路径和是否一样,
     * 答案是显然的,就是一样的,因此我们可以对状态转移的方向进行修改,即我们可以从最下面的一行往最上面走,
     * 这样子我们最后的遍历最后一行找最小值就可以省略了,因为第一行只有一格,最后 dp[0] 即表示的是最小值.
     * 这样子做了之后,我们还可以得到以下两个好处
     * 1. dp 数组不用初始化了,我们只需要定义 dp 数组的长度为 len+1,同时 dp 数组中的值全为 0,就相当于
     *    给原三角形加一行,且该行全为 0,即不对结果造成影响
     * 2. 我们在状态转移的时候不需要进行分类讨论了,因为无论 j 和 i 的关系如何
     *    dp[j] = Math.min(dp[j+1], dp[j]) + triangle.get(i).get(j)
     *    一直成立,不会出现越界的情况.
     * @param triangle
     * @return
     */
    public int minimumTotal3(ArrayList<ArrayList<Integer>> triangle) {
        //检验合法性
        if (triangle == null || triangle.size() == 0) {
            return -1;
        }
        int len = triangle.size();
        int[] dp = new int[len+1];
        //状态转移
        for (int i = len-1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j+1], dp[j]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}
